package com.leetcode.algorithm.y22.m08.w1;

import java.util.LinkedList;
import java.util.Queue;

import com.leetcode.algorithm.y19.m03.Node;

/**
 * 117. 填充每个节点的下一个右侧节点指针 II
 * 
 * https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/
 * 
 * @author jie.deng
 *
 */
class Question0117Solution01 {

	public Node connect(Node root) {
		if (root == null) {
			return root;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			Node prev = null;

			for (int i = 0; i < size; i++) {
				Node node = queue.poll();
				if (prev != null) {
					prev.next = node;
				}
				prev = node;
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}

		}
		return root;
	}

}